package common;


import ap.BDDACLWrapper;
import common.countClass.CIBLine;
import common.countClass.firstCountLine;
import common.countClass.historyHalfLine;
import jdd.bdd.BDD;

import java.io.File;
import java.lang.management.ManagementFactory;
import com.sun.management.OperatingSystemMXBean;
import java.util.*;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;


public class Node extends Thread {
    protected Device d;
    public int index;
    protected HashSet<NodePointer> next;
    protected HashSet<NodePointer> prev;
    Requirement requirement;

    protected final BDD bdd;
    protected Thread th;
    protected HashMap<FIB, HashSet<String>> needNext;

    protected BlockingQueue<MessageData> msgQueue;

    protected HashMap<String, HashSet<FIB>> nodeToFib;
    int needPacket;
    HashMap<FIB, Boolean> needFib;

    public HashMap<Integer, Vector<Integer>> res;

    // quick verify
    HashMap<String, Boolean> verifyResult;
    HashMap<String, Integer> verifyValue;

    //------------------------------------------------------------ 2 -------------------------------------------------------------------------//
    //（1）收到数据包后记录所收到的数据包
    protected HashMap<String, Vector<Announcement>> tablePort;
    protected HashMap<String, CIBIO> previousTablePort;   //PORT

    protected HashSet<FIB> fibFinish;

    protected String dstPort;
    protected HashMap<Integer, Vector<Integer>> showTb;


    //发一个计算一个
    protected HashMap<Integer,CIBLine> CIB;  //id唯一
    protected HashMap<CIBLine,Vector<firstCountLine>> cibHis;
    protected CIBIO iniCo;
    protected CIBIO cibOut;   //发送给上游的
    protected Integer indexOfCib=0;   //CIB的id
    protected HashSet<Announcement> cibEnd;
    protected HashMap<Integer,CIBLine> oldCIB;
    //更新FIB
    protected HashMap<FIB,HashSet<Integer>> FIBHistory; // f id
    HashSet<Announcement> cibOutTmp;
    HashSet<Announcement> oldCibOutTmp;
    int indexOfMergeCib=0;


    //判断是否是最终节点
    protected boolean ifEnd=false;

    //second --收到新的数据包
    protected boolean second=false;

    //判断是否调用了incremental 函数
    boolean hasCallIncremental=false;

    public String getNodeName(){
        return String.format("%s-%s",d.name, index);
    }

    public static void main(String[] args) {

    }


    public Node(Device d, int index, Requirement req) {
        super(String.format("node:%s-%s", d.name, index));
        this.d = d;
        this.index = index;
        this.requirement = req;
        next = new HashSet<>();
        prev = new HashSet<>();
        bdd = d.bddEngine.getBDD();
        //------------------------------------------------------------ 2 -------------------------------------------------------------------------//
        tablePort = new HashMap<>();
        previousTablePort = new HashMap<>();

        fibFinish = new HashSet<>();
        msgQueue = new LinkedBlockingQueue<>();
        nodeToFib = new HashMap<>();
        needNext = new HashMap<>();
        needPacket = 0;
        needFib = new HashMap<>();
        verifyResult = new HashMap<>();
        verifyValue = new HashMap<>();
        showTb=new HashMap<>();


        //cib
        CIB=new HashMap<>();
        cibOut = new CIBIO();
        cibHis=new HashMap<>();
        iniCo=new CIBIO();
        indexOfCib=0;
        FIBHistory=new HashMap<>();
        cibEnd=new HashSet<>();
        oldCIB=new HashMap<>();
        //merge
        cibOutTmp=new HashSet<>();
        oldCibOutTmp=new HashSet<>();

    }
    public Node(Device d, int index) {
        super(String.format("node:%s-%s", d.name, index));
        this.d = d;
        this.index = index;
        next = new HashSet<>();
        prev = new HashSet<>();
        bdd = d.bddEngine.getBDD();
        //------------------------------------------------------------ 2 -------------------------------------------------------------------------//
        tablePort = new HashMap<>();
        previousTablePort = new HashMap<>();

        fibFinish = new HashSet<>();
        msgQueue = new LinkedBlockingQueue<>();
        nodeToFib = new HashMap<>();
        needNext = new HashMap<>();
        needPacket = 0;
        needFib = new HashMap<>();
        verifyResult = new HashMap<>();
        verifyValue = new HashMap<>();
        showTb=new HashMap<>();


        //cib
        CIB=new HashMap<>();
        cibOut = new CIBIO();
        cibHis=new HashMap<>();
        iniCo=new CIBIO();
        indexOfCib=0;
        FIBHistory=new HashMap<>();
        cibEnd=new HashSet<>();
        oldCIB=new HashMap<>();
        //merge
        cibOutTmp=new HashSet<>();
        oldCibOutTmp=new HashSet<>();
    }


    //-------------------------------------------------------------


    //新函数:收到一个数据包就执行一次，对于其中每个FIB都要做一次
    public void deviceDone(String srcPort, CIBIO ci, String id) {
        if(ifEnd) {
            showResult(srcPort,ci, id);
            return;
        }
        if(ci.packetSpace != 0 )requirement.packetSpace = ci.packetSpace;
        recordPacketForHistory(srcPort,ci);   //收到数据包，做好记录，初步计算中间结果
        // 计算所有收到的计数数据包--FIB分开进行
        updateCountCib(srcPort,ci);
        if(msgQueue.isEmpty()&&fibFinish.size()==d.fibs.size())   //变化后更新：消息队列
            Result(id);
    }


    public void recordPacketForHistory(String srcPort,CIBIO ci){
        if(previousTablePort.get(srcPort)==null) {
            tablePort.put(srcPort,ci.announcements);
            previousTablePort.put(srcPort,ci);
        }else {
            if (!ci.equals(previousTablePort.get(srcPort))) {

                previousTablePort.put(srcPort,ci);
                //更新tp，保持最新---  保证存储的是下游的完整的CIB
                Vector<Announcement> oldAn=new Vector<>(tablePort.get(srcPort));
                for(Announcement i:oldAn){
                    if(ci.withdraw.contains(i.id)){
                        tablePort.get(srcPort).remove(i);  //移除变化的
                    }
                }
                tablePort.get(srcPort).addAll(ci.announcements); //新的

                //收到变化的cibIn开始更新
                HashMap<Integer,CIBLine> newC=new HashMap<>(CIBUpdate(CIB,srcPort, ci));
                CIB.clear();
                CIB.putAll(newC);   //第二次收到变化的table，所以要更新

            }
            second = true;
        }
    }


    public void updateCountCib(String srcPort,CIBIO ci) {   //计算第一次
        if (!second) {
            if(!nodeToFib.containsKey(srcPort)){
                System.err.println(srcPort);
                System.out.println(d.fibs);
            }
            for (FIB f : nodeToFib.get(srcPort)) {   //所有含有当前srcPort的fib才进行以下操作

                if (!fibFinish.contains(f)) {                          //本轮已经计算的FIB不会再被计算
                    //第一次计算: 来一个计算一个
                    cibHis=countOneByOne(oldCIB,cibHis,srcPort, ci);
                    if (tablePort.keySet().containsAll(needNext.get(f))) {  //数据包来齐了就认为计算完成了
                        fibFinish.add(f);
                    }
                }
            }
            if(d.fibs.size()==fibFinish.size()) {   //第一次计算
                HashMap<Integer,CIBLine> ic=new HashMap<>(updateCIBFromCibHis(CIB,oldCIB,cibHis)); //FIB--CIB--cibHis--CIB CIBOut
                CIB.clear();
                CIB.putAll(ic);
            }
        }
    }

    //收到一个数据包就计算一个    cibHis-->update CIB  CIBOut
    public HashMap<CIBLine,Vector<firstCountLine>> countOneByOne(HashMap<Integer,CIBLine> oldCIB,HashMap<CIBLine,Vector<firstCountLine>> cibHis,String src,CIBIO cin){  //第一次发送过来，来一个计算一个
        for(CIBLine r:oldCIB.values()) {              //oldCIB：该节点的第一个CIB
            Vector<firstCountLine> re = new Vector<>();
            if (r.action.contains(src)) {   //needNext
                Vector<firstCountLine> result = new Vector<>(cibHis.get(r));  //记录每一个r的上一个计算完成的最新结果
                for (firstCountLine i : result) {
                    for (Announcement a : cin.announcements) {
                        firstCountLine al = new firstCountLine();
                        synchronized (bdd) {
                            al.predicate = bdd.ref(bdd.and(a.predicate, i.predicate));
                        }

                        if (al.predicate != BDDACLWrapper.BDDFalse) {
                            HashSet<Integer> s = new HashSet<>();
                            if (r.type.equals("ANY")) {
                                s.addAll(i.count);
                                s.addAll(a.count);
                            } else {
                                if (r.type.equals("ALL")) {
                                    for (Integer j : a.count) {
                                        for (Integer k : i.count) {
                                            s.add(k + j);
                                        }
                                    }
                                }
                            }

                            al.count.addAll(s);
                            Collections.sort(al.count);
                            historyHalfLine h = new historyHalfLine(a.id, a.count);
                            al.history.put(src, h);
                            al.history.putAll(i.history);
                            al.id = indexOfCib++;
                            re.add(al);
                        }
                    }
                }
                if(re.size()>0)
                {
                    cibHis.put(r, re);
                }
            }
        }
        return cibHis;
    }


    //FIB-->初始化CIB-->初始化cibHis-->收到数据包，第一次计数：计算cibHis-->更新CIB 得到CIBOut
    public HashMap<Integer,CIBLine> updateCIBFromCibHis(HashMap<Integer,CIBLine> CIB,HashMap<Integer,CIBLine> oldCIB,HashMap<CIBLine,Vector<firstCountLine>> cibHis){

        //更新FIBHistory
        for(FIB f:FIBHistory.keySet()) {
            HashSet<Integer> id = new HashSet<>(FIBHistory.get(f)); //原始CIB
            FIBHistory.get(f).clear();
            for (Integer i : id) {
                for (CIBLine r : cibHis.keySet()) {
                    if (r.id == i) {
                        for (firstCountLine s : cibHis.get(r)) {
                            if (s.predicate != BDDACLWrapper.BDDFalse) {
                                FIBHistory.get(f).add(s.id);
                            }
                        }
                    }
                }
            }
        }

        for(CIBLine r:oldCIB.values()){
            if(cibHis.get(r)!=null) {
                for (firstCountLine fr : cibHis.get(r)) {
                    if (fr.predicate != BDDACLWrapper.BDDFalse) {
                        CIBLine c = new CIBLine(fr.id, fr.predicate, r.type, r.action, fr.count, fr.history);
                        synchronized (bdd){
                            bdd.ref(fr.predicate);
                        }
                        CIB.put(fr.id, c);
                    }
                }
            }
        }

        for(CIBLine r:CIB.values()){
            cibOut.announcements.add(new Announcement(r.id, r.predicate, r.count));
        }

        cibHis.clear();
        cibOut.withdraw=new ArrayList<>();
        return CIB;
    }

    //计算每一个r的计数向量--全部重算
    public Vector<Integer> reComputeCount(String type,HashMap<String,historyHalfLine> his){
        Vector<Integer> v=new Vector<>();
        Vector<Integer> tmp=new Vector<>();
        tmp.add(0);
        HashSet<Integer> vec=new HashSet<>();
        if(type.equals("ANY")){
            for(String s:his.keySet()){
                vec.addAll(his.get(s).count);
            }
        }else {
            if(type.equals("ALL")){
                for(String s:his.keySet()) {
                    v.clear();
                    for (Integer i : his.get(s).count) {
                        for (Integer j : tmp) {
                            v.add(i + j);
                        }
                        tmp.clear();
                        tmp.addAll(v);
                    }
                }
                vec.addAll(v);
                v.clear();
            }
        }
        v.addAll(vec);
        Collections.sort(v);
        return v;
    }

    //------------------------------- change: predicate from port A to port B ---------------------------------

    //把下游为oldPort 或 newPort的CIB全部删除，再把下游为oldPort 或 newPort的LEC全部重新计算 drop项单独处理
    public void getChangeToUpdateCIB(List<Change> changeList,String id){
        //System.out.println("getChangeToUpdateCIB");   //modify 不调用
        synchronized (bdd){
            updateNodeToFib();   //保证每次的needNext是最新的 todo 调用
        }
        if(ifEnd || next.size() == 0){   //todo 起点或者终点改变LEC，直接显示结果
            showResult(id);
            return;
        }
        hasCallIncremental=true;  //此时收到一个数据包计算更新完马上发送出去


        HashMap<Integer,CIBLine> newC=new HashMap<>(changeToCIB(changeList,requirement.packetSpace,tablePort,CIB));
        CIB.clear();
        CIB.putAll(newC);

        //是否需要merge，是否需要向上游发送更新结果
        Result(id);
    }



    //------------------------------------- 收到变化的table的处理方式 -------------------------------------

    public HashMap<Integer, CIBLine> CIBUpdate(HashMap<Integer, CIBLine> cibNeedToUpdate, String srcNode, CIBIO cibIn){   //更新的算法1:返回发送的内容               //todo 消息队列取出全部计算完成再发送

        HashMap<Integer, CIBLine> cibNeedChange=new HashMap<>();
        HashMap<Integer, CIBLine> newCIB=new HashMap<>(cibNeedToUpdate);
        if(cibIn.withdraw==null){
            System.out.println("false4");
            cibNeedChange.putAll(cibNeedToUpdate);
        }else{
            for(CIBLine r:cibNeedToUpdate.values()) {
                //发送过来的withdraw.id 存在于history
                if (r.action.contains(srcNode)) {
                    if(r.his.get(srcNode)!=null) {
                        if (cibIn.withdraw.contains(r.his.get(srcNode).id)) {      //获取变化的CIB
                            cibNeedChange.put(r.id, r);
                        }
                    }
                }
            }
        }
        cibOut.withdraw.addAll(cibNeedChange.keySet());                              //要删除的

        HashMap<Integer, CIBLine> cibChangeDone=new HashMap<>(getCIBChangeNode(cibNeedChange,cibIn,srcNode));

        newCIB.putAll(cibChangeDone);                                                     //新增的CIB

        for(FIB f:FIBHistory.keySet()) {
            for (Integer i : cibNeedChange.keySet()) {
                if (FIBHistory.get(f).contains(i)) {
                    FIBHistory.get(f).remove(i);         //删除这条CIB.id = i
                    for (CIBLine r : cibHis.keySet()) {
                        if (r.id == i) {                 //增加i变化后得到的CIB的id
                            for (firstCountLine s : cibHis.get(r)) {
                                if (s.predicate != BDDACLWrapper.BDDFalse) {
                                    FIBHistory.get(f).add(s.id);                      //更新FIBHistory
                                }
                            }
                        }
                    }
                }
            }
        }
        cibHis.clear();

        for(CIBLine c:cibChangeDone.values()){
            Announcement a = new Announcement(c.id, c.predicate, c.count);
            cibOut.announcements.add(a);
        }

        return newCIB;
    }


    public HashMap<Integer, CIBLine> getCIBChangeNode(HashMap<Integer, CIBLine> cibNeedChange, CIBIO ci, String srcName){   //更新的算法2
        HashMap<Integer, CIBLine> cibChangeDone=new HashMap<>();
        int k=0;
        for(CIBLine r:cibNeedChange.values()) {
            Vector<firstCountLine> re=new Vector<>();
            CIBLine rr=new CIBLine(r.id,r.predicate,r.type,r.action,r.count,r.his);

            for (Announcement a : ci.announcements) {    //ci.an=null  发送announcement=null
                CIBLine c=new CIBLine();
                synchronized (bdd){
                    c.predicate = bdd.ref(bdd.and(r.predicate, a.predicate));
                }
                if (c.predicate != BDDACLWrapper.BDDFalse) {
                    c.type=r.type;
                    c.id=indexOfCib++;
                    c.action = r.action;
                    //必定属于r.history
                    c.his=new HashMap<>(r.his);
                    historyHalfLine h=new historyHalfLine(a.id,a.count);
                    c.his.put(srcName,h);
                    c.count = reComputeCount(c.type,c.his);

                    synchronized (bdd){
                        int pre=bdd.ref(bdd.not(c.predicate)); //差集：减去共同部分
                        r.predicate=bdd.ref(bdd.and(pre,r.predicate));
//                        bdd.deref(pre);
                    }
                    cibChangeDone.put(c.id,c);
                    re.add(new firstCountLine(c.id,c.predicate,c.count,c.his));
                }
            }
            cibHis.put(rr,re);   //凡是产生新的CIB，都会记录在cibHis，直到更新了FIBHistory才会删除其中的记录
            if(r.predicate==BDDACLWrapper.BDDFalse){
                k++;
            }else
            {
                d.println("cib update false");
            }
        }
        if(k!=cibNeedChange.size()){
            d.println("false");
        }

        return cibChangeDone;
    }


//---------------------------------------------------------初始化+结果------------------------------------------------------

    public void updateNodeToFib(){
        nodeToFib.clear();
        fibFinish.clear();
        needNext.clear();
        needPacket = 0;
        needFib.clear();

        HashSet<String> nextSet = new HashSet<>();
        for(NodePointer n:next){
            nextSet.add(n.name);
            nodeToFib.put(n.name, new HashSet<>());  //与dv net相关
        }

        for(FIB fib:d.fibs){
            HashSet<String> f = new HashSet<>(nextSet);
            for(String s:nextSet){
                if(!fib.forward.contains(s)){
                    f.remove(s);
                }
            }
            needNext.put(fib, f);  //FIB需要的下游
           /* if(f.size() == 0){                    //fib变化后，可能会出现fib port为空的情况，因此要避免
                fibFinish.add(fib);  //每次变化都会运行的
            }*/
            for(String s: nextSet){
                if(fib.forward.contains(s)) {
                    nodeToFib.get(s).add(fib);
                    needFib.put(fib, false);
                }
            }
        }

        HashSet<String> needSet = new HashSet<>();

        for(String s: nodeToFib.keySet()){
            if(nodeToFib.get(s).size() > 0) {
                needPacket++;
                needSet.add(s);
                verifyValue.put(s, 0);
                verifyResult.put(s, false);
            }
        }
//        qv.setElement(needSet);

    }

    //FIB-->初始化CIB-->初始化cibHis-->收到数据包，第一次计数：计算cibHis-->更新CIB 得到CIBOut
    public void run(){
        synchronized (bdd){
            updateNodeToFib();
        }
        if(prev.size()==0){
            ifEnd=true;
        }
        initializeCIB(requirement.packetSpace);
        runDevice();
    }

    //初始化CIB  FIBHistory  cibHis
    public void initializeCIB(int packetSpace){
        //indexOfCib=0;
        int dropId=-1;
        oldCIB.clear();
        CIB.clear();
        cibHis.clear();
        fibFinish.clear();

        for(FIB f:d.fibs) {
            int pre=0;
            synchronized (bdd) {
                pre = bdd.ref(bdd.and(f.predicate, packetSpace));  //f.predicate==BDDACLWrapper.BDDFalse：不做操作
            }
            //交集，加CIB--type+forward=drop history=null 0  size=0---drop
            if ( pre!= BDDACLWrapper.BDDFalse) {
                if(needNext.get(f).size()==0){    //drop：已经创建那就合并，否则创建
                    if(dropId>-1){
                        int orPre=0;
                        synchronized (bdd){
                            orPre=bdd.orTo(CIB.get(dropId).predicate,pre);
                        }
                        CIB.put(dropId,new CIBLine(dropId,orPre,"drop",new HashSet<>()));
                    }else
                    {
                        dropId=indexOfCib++;
                        CIBLine c = new CIBLine(dropId, pre, "drop", new HashSet<>());  //action为空的，history为空
                        CIB.put(c.id, c);     //初始化，count=[0] history=null，不需要参与计算的CIB
                        // todo 所有变化从change 进行,不需要FIBHistory了？

                    }
                    fibFinish.add(f);
                }else {
                    CIBLine c = new CIBLine(indexOfCib++, pre, String.valueOf(f.type), needNext.get(f));
                    oldCIB.put(c.id, c);  //要参与计算的LEC，计算完成就更新到CIB中
                    HashSet<Integer> h = new HashSet<>();
                    h.add(c.id);
                    FIBHistory.put(f, h);

                    Vector<firstCountLine> result = new Vector<>();
                    firstCountLine al = new firstCountLine(c.id, c.predicate);//vector=[0]  history为null
                    synchronized (bdd) {
                        bdd.ref(c.predicate);
                    }
                    result.add(al);
                    cibHis.put(c, result);//每一条cib都非空
                }
            }else
            {
                fibFinish.add(f);
            }
        }
    }

    public void runDevice(){
        th = Thread.currentThread();
        d.addRecord("0", index, "* cib", CIB.size());
        MessageData md;

        while(true){
            try {
                md = msgQueue.take();
            } catch (InterruptedException e) {
                break;
            }
            if(md.type == 0){
                long t1 = System.nanoTime();

                d.printf("%s <- %s-%s, %s\n", getNodeName(), md.np.name, md.np.index, md.ci);
                //System.out.printf("%s <- %s-%s, %s\n", getNodeName(), md.np.name, md.np.index, md.ci);

                deviceDone(md.np.name, md.ci, md.id);
                long t2 = System.nanoTime();
                double f = (t2-t1) ; // ms

//                d.addRecord(md.id, index, "count compute", f);
            }else if(md.type == 1){
                updateNodeToFib();
                ifChangeFib(md.oldFib, md.id);
            }
        }
    }


    public void Result(String id) {          //是否发消息

        if(!hasCallIncremental) {   //第一次初始化才需要判断
            if (fibFinish.size() < d.fibs.size()) {
                d.println(getNodeName() + "应处理的数据包:" + d.fibs.size() + "  当前处理:" + fibFinish.size());
                for (FIB fib : d.fibs)
                    if (!fibFinish.contains(fib)) d.printf("%s ", fib.forward);
                d.println();
                return;
            }
        }

        sendResult(id);
    }



    public HashMap<Integer,Vector<Integer>> sortResult(CIBIO ci){
        HashSet<Announcement> ce=new HashSet<>(cibEnd);
        if(ci.withdraw.size()>0) {
            for(Announcement a:ce)
            {
                if(ci.withdraw.contains(a.id))
                {
                    cibEnd.remove(a);   //删除withdraw部分
                }
            }
        }
        cibEnd.addAll(ci.announcements);
        return getTb();
    }

    public HashMap<Integer,Vector<Integer>> getTb(){
        HashMap<Integer,Vector<Integer>> tb=new HashMap<>();
        Vector<Integer> v=new Vector<>();
        v.add(0);
        for (Announcement i : cibEnd) {
            if ((!i.count.equals(v)) && i.predicate != BDDACLWrapper.BDDFalse) {
                tb.put(i.predicate, i.count);
            }
        }
        if (tb.size() == 0) {      //发送来的table为 [1]={0}
            tb.put(1, v);
        }
        return tb;
    }

    public void showResult(String srcPort, CIBIO ci, String id) { //只显示predicate count 部分，id不需要
        HashMap<Integer,Vector<Integer>> tb=new HashMap<>(sortResult(ci));

        long end = System.nanoTime();

        d.println("最终源点的计数向量结果：");
        d.println("destination: "+srcPort);

        res=new HashMap<>();
        showTb=new HashMap<>();
        res.putAll(tb);
        dstPort=srcPort;
        showTb.putAll(tb);

        if(d.output) Utility.printCount(tb, bdd);
        d.addRecord(id, index, "*count finish", end);
    }


   //--------------------------------- incremental update 相关函数 ------------------------------------
    public HashMap<Integer, CIBLine> changeToCIB(List<Change> changeList, int packetSpace, HashMap<String,Vector<Announcement>> tablePort, HashMap<Integer, CIBLine> CIB){
        int dropPredicate=-1;
        int dropId=-1;
        HashSet<Integer> delCIB=new HashSet<>();
        HashSet<FIB> lecChange=new HashSet<>();
        HashSet<FIB> mayLecChange=new HashSet<>(getLecInPacketSpace(packetSpace));   //f.forward=needNext.get(f)


        for(Change c:changeList) {
            int pre = 0;
            synchronized (bdd) {
                pre = bdd.ref(bdd.and(packetSpace, c.predicate));
            }
            if (pre != BDDACLWrapper.BDDFalse) {
                HashSet<CIBLine> cibTmp = new HashSet<>(CIB.values());
                boolean existNewPort = false;
                boolean existOldPort = false;

                if(tablePort.get(c.newPort)!=null){
                    existNewPort = true;
                }
                if(tablePort.get(c.oldPort)!=null){
                    existOldPort = true;
                }

                //1、计算变化的LEC前更新CIB
                if(existNewPort||existOldPort) {
                    for (CIBLine r : cibTmp) {
                        if (r.action.contains(c.newPort)||r.action.contains(c.oldPort)) {  //r.action==needNext
                            delCIB.add(r.id);
                        }
                        if (dropId==-1&&r.type.equals("drop")) {   //记录原本CIB的drop 项 id predicate
                            dropId = r.id;
                            dropPredicate=r.predicate;
                        }
                    }
                }
                else{   //全为drop，不操作
                    System.out.println("continue");
                    continue;
                }
                if (!existNewPort) {
                    if (dropId == -1) {  //此前没有则新建，应该不会存在这种情况吧（或很少--起始必定创建一项）
                        dropId=indexOfCib++;
                        CIB.put(dropId, new CIBLine(dropId, pre, "drop", new HashSet<>()));     //初始化，count=[0] history=null，不需要参与计算的CIB
                    } else               //合并
                    {
                        int orP;
                        synchronized (bdd) {
                            orP = bdd.orTo(pre, CIB.get(dropId).predicate);
                        }
                        CIB.put(dropId, new CIBLine(dropId, orP, "drop", new HashSet<>()));
                    }
                }
                if (!existOldPort) {   //分割，必定存在drop中
                    int notP;
                    int dropP;
                    synchronized (bdd){
                        notP=bdd.ref(bdd.not(pre));
                        dropP=bdd.ref(bdd.and(notP,CIB.get(dropId).predicate));
                    }
                    if(dropP==BDDACLWrapper.BDDFalse) {
                        CIB.remove(dropId);
                        dropId=-1;
                        dropPredicate=-1;
                    }else{
                    CIB.put(dropId, new CIBLine(dropId, dropP, "drop", new HashSet<>()));
                    }
                }

                //2、获取需要重新计算的LEC
                for(FIB f:mayLecChange){
                    if(f.forward.contains(c.oldPort)||f.forward.contains(c.newPort)){  //todo verify
                        lecChange.add(f);
                    }
                }
            }
        }


        //3、计算变化的LEC的count值,新的CIB中不会有drop项（needNext必定不为空）
        HashMap<Integer, CIBLine> CIBChange=new HashMap<>(countNewLec(lecChange,tablePort));


        //4、计算后更新CIB--当前变化后的最全新的CIB，并获取最新发送的信息
        cibOut.withdraw.clear();
        cibOut.announcements.clear();

        for(Integer i:delCIB){
            CIB.remove(i);
            cibOut.withdraw.add(i);
        }
        //增加新增的
        for(CIBLine r:CIBChange.values()) {
            if (r.type.equals("drop")) {
                int orP=r.predicate;
                if(dropId==-1) {  //首次创建
                    dropId = indexOfCib++;
                    dropPredicate=-1;
                }else {
                    synchronized (bdd) {
                        orP = bdd.orTo(r.predicate, CIB.get(dropId).predicate);
                    }
                }
                CIB.put(dropId, new CIBLine(dropId, orP, "drop", new HashSet<>()));

            } else
            {
                CIB.put(r.id,r);
            }
        }


        for(CIBLine c:CIBChange.values()){
            Announcement a=new Announcement(c.id,c.predicate,c.count);
            cibOut.announcements.add(a);
        }

        if(dropId>-1&&CIB.get(dropId).predicate!=dropPredicate){  //drop项有变化
            if(dropPredicate!=-1) {
                cibOut.withdraw.add(dropId);  //不是刚创建的项
                CIBLine r = new CIBLine(indexOfCib++, CIB.get(dropId).predicate, "drop", new HashSet<>());
                CIB.put(r.id, r);
                CIB.remove(dropId);
                cibOut.announcements.add(new Announcement(r.id,r.predicate,r.count));
            }else
            {
                cibOut.announcements.add(new Announcement(CIB.get(dropId).id,CIB.get(dropId).predicate,CIB.get(dropId).count));
            }
        }

        return CIB;
    }

    //初步得到与全集packetSpace有关的LEC
    public HashSet<FIB> getLecInPacketSpace(int packetSpace){
        HashSet<FIB> mayChangeLec=new HashSet<>();
        for(FIB f:d.fibs){
            int newPredicate=0;
            synchronized (bdd){
                newPredicate=bdd.ref(bdd.and(f.predicate,packetSpace));
            }
            if(newPredicate!=BDDACLWrapper.BDDFalse){
                FIB newFib=new FIB(f,newPredicate,needNext.get(f));   //将当前f的predicate改为newPredicate，forward改为needNext.get(f)
                mayChangeLec.add(newFib);  //若needNext为空，实际上就是不包含oldPort newPort，那就不需要改变
            }
        }
        return mayChangeLec;
    }

    //变化的LEC重新计算count值
    public HashMap<Integer, CIBLine> countNewLec(HashSet<FIB> changeLec, HashMap<String,Vector<Announcement>> tablePort){
        HashMap<Integer, CIBLine> vc = new HashMap<>();
        for(FIB f:changeLec) {
            CIBLine r = new CIBLine(indexOfCib++, f.predicate, String.valueOf(f.type), f.forward); //此时f.predicate为它与packet space的交集，f.forward实际上是needNext()
            Vector<firstCountLine> res = new Vector<>();
            firstCountLine acl = new firstCountLine(r.id, r.predicate);//vector=[0]  his=null
            res.add(acl);
            cibHis.put(r, res);

            for (String fw : f.forward) {
                if (tablePort.get(fw) == null) {
                    System.out.println("false1");
                    return vc;
                }
                Vector<firstCountLine> re = new Vector<>();
                Vector<firstCountLine> result = new Vector<>(cibHis.get(r));  //记录每一个r的上一个计算完成的最新结果
                for (firstCountLine i : result) {
                    for (Announcement a : tablePort.get(fw)) {
                        firstCountLine al = new firstCountLine();
                        synchronized (bdd) {
                            al.predicate = bdd.ref(bdd.and(a.predicate, i.predicate));
                        }
                        if (al.predicate != BDDACLWrapper.BDDFalse) {
                            HashSet<Integer> s = new HashSet<>();
                            if (r.type.equals("ANY")) {
                                s.addAll(i.count);
                                s.addAll(a.count);
                            } else {
                                if (r.type.equals("ALL")) {
                                    for (Integer j : a.count) {
                                        for (Integer k : i.count) {
                                            s.add(k + j);
                                        }
                                    }
                                }
                            }
                            al.count.addAll(s);
                            Collections.sort(al.count);
                            historyHalfLine h = new historyHalfLine(a.id, a.count);
                            al.history.put(fw, h);
                            al.history.putAll(i.history);
                            al.id = indexOfCib++;
                            re.add(al);
                        }
                    }
                }
                if (re.size() > 0) {
                    cibHis.put(r, re);
                } else {
                    System.out.println("false2");
                }
            }

            //CIBChange
            for (firstCountLine fi : cibHis.get(r)) {
                CIBLine c = new CIBLine(fi.id, fi.predicate, r.type, r.action, fi.count, fi.history);
                vc.put(fi.id, c);
            }
        }
        return vc;  //新增
    }

    //merge
    public HashSet<Announcement> mergeCib(HashSet<Announcement> oldCibOutTmp)
    {
        //oldCibOutTmp维持当前最新全集
        //cibOutTmp 当前更新的部分的merge结果
        cibOutTmp.clear();
        if(oldCibOutTmp==null){
            oldCibOutTmp=new HashSet<>();
        }
        HashSet<Announcement> oldTmp = new HashSet<>();
        if(oldCibOutTmp.size()>0){
            oldTmp = new HashSet<>(oldCibOutTmp);  //上次的
        }
        if(cibOut.announcements.size()>0) {
            cibOutTmp.add(new Announcement(indexOfMergeCib++, cibOut.announcements.get(0).predicate, cibOut.announcements.get(0).count));
            for (Announcement a : cibOut.announcements) {
                if (a.equals(cibOut.announcements.get(0)))
                    continue;
                HashSet<Announcement> tmp = new HashSet<>(cibOutTmp);
                boolean flag = true;
                int pre;
                for (Announcement b : tmp) {
                    if (b.count.equals(a.count)) {    //count
                        flag = false;
                        synchronized (bdd) {
                            pre = bdd.ref(bdd.or(a.predicate, b.predicate));  //predicate or
                            //bdd.deref(b.predicate);
                        }
                        cibOutTmp.add(new Announcement(b.id, pre, b.count));
                        cibOutTmp.remove(b);
                    }
                }
                if (flag) {
                    cibOutTmp.add(new Announcement(indexOfMergeCib++, a.predicate, a.count));
                }
            }
            cibOut.announcements.clear();
        }else
        {
            cibOut.withdraw.clear();
        }


        if (oldCibOutTmp.size() == 0) {
            cibOut.withdraw = new ArrayList<>();
            cibOut.announcements.addAll(cibOutTmp);
            oldCibOutTmp.addAll(cibOutTmp);  //最新全集
        } else {

            for (Announcement a : cibOutTmp) {
                boolean flag = true;
                for (Announcement b : oldTmp) {
                    if (a.count.equals(b.count)) {
                        flag = false;
                        break;
                    }
                }
                HashSet<Announcement> oc = new HashSet<>(oldCibOutTmp);
                if (flag) {   //全新的count值
                    for (Announcement c : oc) {
                        int p = 0;
                        synchronized (bdd) {
                            p = bdd.ref(bdd.and(c.predicate, a.predicate));
                        }
                        if (p != BDDACLWrapper.BDDFalse) {
                            //去掉分离的部分
                            int predicate = 0;
                            synchronized (bdd) {
                                int pre = bdd.ref(bdd.not(p));
                                predicate = bdd.ref(bdd.and(pre, c.predicate));
                            }
                            if (predicate != BDDACLWrapper.BDDFalse) {
                                oldCibOutTmp.add(new Announcement(indexOfMergeCib++, predicate, c.count));
                            }
                            oldCibOutTmp.remove(c);
                        }
                    }
                    //增加全新计数值
                    oldCibOutTmp.add(a);
                } else   //不是全新的计数值，找相同的合并
                {
                    for (Announcement c : oc) {
                        if (c.count.equals(a.count)) {
                            int q = 0;
                            synchronized (bdd) {
                                q = bdd.ref(bdd.and(a.predicate, c.predicate));
                            }
                            if (q != a.predicate) {
                                synchronized (bdd) {
                                    q = bdd.orTo(a.predicate, c.predicate);
                                }
                                oldCibOutTmp.add(new Announcement(indexOfMergeCib++, q, a.count));
                                oldCibOutTmp.remove(c);
                            }
                        } else {
                            int p = 0;
                            synchronized (bdd) {
                                p = bdd.ref(bdd.and(c.predicate, a.predicate));
                            }

                            if (p != BDDACLWrapper.BDDFalse) {   //要割离
                                int predicate = 0;
                                synchronized (bdd) {
                                    int pre = bdd.ref(bdd.not(p));
                                    predicate = bdd.ref(bdd.and(pre, c.predicate));
                                }
                                if (predicate != BDDACLWrapper.BDDFalse) {
                                    oldCibOutTmp.add(new Announcement(indexOfMergeCib++, predicate, c.count));
                                }
                                oldCibOutTmp.remove(c);
                            }
                        }
                    }
                }
            }

            //最终确定发送的部分
            cibOut.announcements.clear();
            cibOut.withdraw.clear();
            HashSet<Announcement> oc = new HashSet<>(oldCibOutTmp);

            for(Announcement a:oc){
                if (a.predicate == BDDACLWrapper.BDDFalse) {
                    oldCibOutTmp.remove(a);
                }
            }


            //withdraw
            for (Announcement b : oldTmp) {
                boolean h = true;
                for (Announcement a : oc) {
                    if (a.count.equals(b.count) && a.predicate == b.predicate) {
                        h = false;
                    }
                }
                if (h) {
                    cibOut.withdraw.add(b.id);
                }
            }


            //announcements
            oc.clear();
            oc = new HashSet<>(oldCibOutTmp);
            for (Announcement a : oc) {
                boolean h = true;
                for (Announcement b : oldTmp) {
                    if (a.count.equals(b.count) && a.predicate == b.predicate) {
                        oldCibOutTmp.remove(a);
                        oldCibOutTmp.add(b);
                        h = false;
                    }
                }
                if(h){
                    cibOut.announcements.add(a);
                }
            }

        }

        return oldCibOutTmp;
        //merge end
    }

    //--------------------------------------------------------- 接收+发送------------------------------------------------------
    public void startCount(){
        if(this.next.size() == 0){
            long t = System.nanoTime();
            d.printf("%s开始发送计数值\n 开始时间为：%s\n", this.d.name, t);
            String id = Utility.getRandomString();

            Announcement a = new Announcement(0, requirement.packetSpace, Utility.getOneNumVector(1));
            Vector<Announcement> al = new Vector<>();
            al.add(a);
            CIBIO CIBOut = new CIBIO(al, new ArrayList<>());
            CIBOut.packetSpace = requirement.packetSpace;
            sendCount(CIBOut, prev, id);

            d.addRecord(id, index, "*count start", t);
        }

    }


    public void sendCount(CIBIO co, Iterable<NodePointer> np, String id){             //todo send receive 函数
        d.sendCount(np, index, co, id);
        d.printf("%s发送CibOut [%s] 下一跳为: %s\n",  getNodeName(), co, np);
        //System.out.printf("%s发送CibOut [%s] 下一跳为: %s\n",  getNodeName(), co, np);
    }


    public void addNext(NodePointer n){
        if(n.name.equals("virtual")) return;
        next.add(n);
    }

    public void addPrev(NodePointer n){
        if(n.name.equals("virtual")) return;
        prev.add(n);
    }

    public HashSet<String> getNextSet(){
        HashSet<String> hs = new HashSet<>();
        for(NodePointer np:next)
            hs.add(np.name);
        return hs;
    }

    public void receiveCount(CIBIO c, NodePointer np,String id){
        MessageData md = new MessageData(c, np, id);
        try {
            msgQueue.put(md);
        } catch (InterruptedException e) {
//            e.printStackTrace();
        }
    }
    public void receiveCount(Vector<FIB> oldFib,String id){
        MessageData md = new MessageData(oldFib, id);
        try {
            msgQueue.put(md);
        } catch (InterruptedException e) {
//            e.printStackTrace();
        }
    }


    public void close(){
        th.interrupt();
    }

    @Override
    public String toString() {
        return getNodeName();
    }

    public static class MessageData{
        public CIBIO ci;
        public NodePointer np;
        public String id;

        public int type;
        public Vector<FIB> oldFib;
        public MessageData(CIBIO c, NodePointer n, String id){
            ci = c;
            np = n;
            this.id = id;
            this.type = 0;
        }

        public MessageData(Vector<FIB> oldFib, String id){
            this.oldFib = oldFib;
            this.id = id;
            this.type = 1;
        }
    }


    public void showResult(String id) { //trace为源主机所有的最终的trace:ANY 满足向量

        long end = System.nanoTime();
        d.println("最终源点的计数向量结果：");
        d.println("destination: "+dstPort);
        res = showTb;
        if(d.output)Utility.printCount(showTb, bdd);
        d.addRecord(id, index, "*count finish", end);

    }

    public void sendResult(String id){    //prev：转发对象

        //全null不发
        if(cibOut.withdraw.size()==0&& cibOut.announcements.size()==0){
            d.println(d.name+index+" 0 both null");
            d.addRecord(id, index, "*finish", System.nanoTime());
            return;
        }
        d.addRecord(id, index, "*cib", CIB.size());

        //更新CIB 原本要发送的要撤回了
        Vector<Integer> del=new Vector<>();
        Vector<Announcement> oldAn = new Vector<>(cibOut.announcements);
        for (Announcement i : oldAn) {
            if (cibOut.withdraw.contains(i.id)) {
                cibOut.announcements.remove(i);
                del.add(i.id);
            }
        }
        if(del.size()>0){
            for(Integer i:del) {
                cibOut.withdraw.remove(i);
            }
        }

        //merge
        HashSet<Announcement> oc=new HashSet<>(mergeCib(oldCibOutTmp));
        oldCibOutTmp.clear();
        oldCibOutTmp.addAll(oc);

        //merge后，全null不发
        if(cibOut.withdraw.size()==0&& cibOut.announcements.size()==0){
            d.println(d.name+index+" 1 both null");
            d.addRecord(id, index, "*finish", System.nanoTime());
            return;
        }


        if (!iniCo.equals(cibOut)) {  //收齐了应该收的数据包计算后+与上一回发送计数结果不同 == 可以发送
            cibOut.packetSpace = requirement.packetSpace;
            sendCount(cibOut, prev, id);
            d.addRecord(id, index, "*count send", System.nanoTime());
            iniCo.announcements.clear();
            iniCo.withdraw.clear();
            iniCo.announcements.addAll(cibOut.announcements);
            iniCo.withdraw.addAll(cibOut.withdraw);
            cibOut.announcements.clear();
            cibOut.withdraw.clear();
        } else {
            d.println(d.name + index + "与上次计数结果一致，本次不再发送");
            if(ifEnd||second)
                d.addRecord(id, index, "*finish", System.nanoTime());
        }
    }

    public void sendResult(String id,String dst){    //prev：转发对象，静态转发节点使用

        //全null不发
        if(cibOut.withdraw.size()==0&& cibOut.announcements.size()==0){
            d.println(d.name+index+" 0 both null");
            d.addRecord(id, index, "*finish", System.nanoTime());
            return;
        }

        //更新CIB 原本要发送的要撤回了
        Vector<Integer> del=new Vector<>();
        Vector<Announcement> oldAn = new Vector<>(cibOut.announcements);
        for (Announcement i : oldAn) {
            if (cibOut.withdraw.contains(i.id)) {
                cibOut.announcements.remove(i);
                del.add(i.id);
            }
        }
        if(del.size()>0){
            for(Integer i:del) {
                cibOut.withdraw.remove(i);
            }
        }

        //merge
        HashSet<Announcement> oc=new HashSet<>(mergeCib(oldCibOutTmp));
        oldCibOutTmp.clear();
        oldCibOutTmp.addAll(oc);

        //merge后，全null不发
        if(cibOut.withdraw.size()==0&& cibOut.announcements.size()==0){
            d.println(d.name+index+" 1 both null");
            d.addRecord(id, index, "*finish", System.nanoTime());
            return;
        }

        CIBIO sendCIBOut;
        cibOut.dst=dst;
        if(hasCallIncremental){
            sendCIBOut=new CIBIO(cibOut.announcements,cibOut.withdraw,cibOut.dst);
        }else
        {
            sendCIBOut=new CIBIO(cibOut.announcements,cibOut.withdraw,cibOut.dst,requirement.packetSpace);  //todo dst获取   map<String,List<NodePointer>>
        }
        if (!iniCo.equals(cibOut)) {  //收齐了应该收的数据包计算后+与上一回发送计数结果不同 == 可以发送
            sendCount(sendCIBOut, prev, id);
            d.addRecord(id, index, "*count send", System.nanoTime());
            iniCo.announcements.clear();
            iniCo.withdraw.clear();
            iniCo.announcements.addAll(cibOut.announcements);
            iniCo.withdraw.addAll(cibOut.withdraw);
            iniCo.dst=d.ip;
            cibOut.announcements.clear();
            cibOut.withdraw.clear();
        } else {
            d.println(d.name + index + "与上次计数结果一致，本次不再发送");
            if(ifEnd||second)
                d.addRecord(id, index, "*finish", System.nanoTime());
        }
    }




    //---------------------------------------- 旧版本 FIB 变化:FIB CIB FIBHistory  -----------------------------------------
    //拿到变化的有影响的FIB
    public Vector<FIB> getFIBChange(Vector<FIB> oldFibs){
        cibOut.announcements.clear();
        cibOut.withdraw.clear();
        Vector<FIB> FIBChange =new Vector<>();
        Vector<FIB> newFIB =new Vector<>();
        Vector<FIB> oldFIB =new Vector<>(oldFibs);
        for(FIB f:d.fibs){
            if(oldFibs.contains(f)){
                fibFinish.add(f);
                oldFIB.remove(f);   //剩下的全部变化到newFIB中
            }else{
                newFIB.add(f);
            }
        }

        //oldFib中剩下的FIB对应的CIB都要删除
        for(FIB f:oldFIB){
            int p=0;
            synchronized (bdd) {
                p = bdd.ref(bdd.and(f.predicate, requirement.packetSpace));
            }
            if(p!=BDDACLWrapper.BDDFalse&&FIBHistory.get(f)!=null) {
                cibOut.withdraw.addAll(FIBHistory.get(f));
            }
            FIBHistory.remove(f);
        }
        //删除已经变化的
        for(Integer i: cibOut.withdraw){
            CIB.remove(i);
        }

        //变化后的FIB：是否对于计数有影响
        for(FIB f:newFIB) {
            int p = 0;
            synchronized (bdd) {
                p = bdd.ref(bdd.and(f.predicate, requirement.packetSpace));
            }
            if (p != BDDACLWrapper.BDDFalse) {
                if (tablePort.keySet().containsAll(needNext.get(f)) && needNext.get(f).size() > 0) {
                    //对本次计数有影响的FIB，后面计算的时候再创建history CIB
                    FIBChange.add(f);
                } else {    //对本次计数没有影响的FIB:创建新的history和CIB
                    if (needNext.get(f).size() == 0) {
                        CIBLine c = new CIBLine(indexOfCib++, f.predicate, String.valueOf(f.type), f.forward);
                        CIB.put(c.id, c);   //初始化，count=[0] history=null
                        HashSet<Integer> h = new HashSet<>();
                        h.add(c.id);
                        FIBHistory.put(f, h);
                        cibOut.announcements.add(new Announcement(c.id, c.predicate, c.count));

                    }
                    fibFinish.add(f);
                }
            }else
            {
                fibFinish.add(f);
            }
        }

        return FIBChange;
    }


    //FIB变化后计算更新CIB-->CIBOut
    public void ifChangeFib(Vector<FIB> oldFibs, String id) {  //某节点自己fwd更新
        long t1 = System.nanoTime();
        long ts = System.nanoTime();

        if(ifEnd || next.size() == 0){
            showResult(id);
            long t2 = System.nanoTime();
            double t = (t2-t1);
//            d.addRecord(id, index, "cib change", t);
        }else {

            //非源点FIB变化，向上游发送变化的CIB
            Vector<FIB> FIBChange=getFIBChange(oldFibs);
            HashMap<Integer, CIBLine> CIBChange=new HashMap<>();

            for(FIB f:FIBChange) {    //重新计算对应的CIB
                if (f.predicate != BDDACLWrapper.BDDFalse) {
                    int pre = 0;
                    synchronized (bdd) {
                        pre = bdd.ref(bdd.and(pre, requirement.packetSpace));
                    }
                    if (pre != BDDACLWrapper.BDDFalse) {
                        FIB newFIB=new FIB(f,pre,needNext.get(f));
                        HashSet<FIB> tmp=new HashSet<>();
                        tmp.add(newFIB);
                        CIBChange = new HashMap<>(countNewLec(tmp,tablePort));
                        CIB.putAll(CIBChange);
                        HashSet<Integer> v = new HashSet<>(CIBChange.keySet());
                        FIBHistory.put(f, v);

                        //获取此时的发送的信息
                        for(CIBLine c:CIBChange.values()){
                            Announcement a=new Announcement(c.id,c.predicate,c.count);
                            cibOut.announcements.add(a);
                        }
                    }
                }
                fibFinish.add(f);
            }

            cibHis.clear();

            long t2 = System.nanoTime();
            double t = (t2-t1);
            Result(id);     //遍历完所有结果判断是否发送结果
//            d.addRecord(id, index, "cib change", t);
        }
        d.addRecord(id, index, "*cib change after lec change start", ts);
    }
}